import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/19 15:57
 * @description 如果查询多，那么每一次查询耗时大，效率低，可以采用 Floyd算法，先对图做预处理
 * Floyd算法适用于 边密集图，
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int idx = 0;
        Map<String, Integer> map = new HashMap<>();
        for (List<String> e: equations) {
            if (!map.containsKey(e.get(0))) {
                map.put(e.get(0), idx++);
            }
            if (!map.containsKey(e.get(1))) {
                map.put(e.get(1), idx++);
            }
        }
        // 邻接矩阵存储图中边权值
        double[][] graph = new double[idx][idx];
        for (int i = 0; i < idx; i++) {
            Arrays.fill(graph[i], -1.0);
        }
        int n = equations.size();
        for (int i = 0; i < n; i++) {
            int va = map.get(equations.get(i).get(0)), vb = map.get(equations.get(i).get(1));
            graph[va][vb] = values[i];
            graph[vb][va] = 1.0 / values[i];
        }

        // floyd
        for (int k = 0; k < idx; k++) {
            for (int i = 0; i < idx; i++) {
                for (int j = 0; j < idx; j++) {
                    if (graph[i][k] > 0 && graph[k][j] > 0) {
                        graph[i][j] = graph[i][k] * graph[k][j];
                    }
                }
            }
        }
        // 查询
        int queriesCount = queries.size();
        double[] ret = new double[queriesCount];
        for (int i = 0; i < queriesCount; i++) {
            List<String> query = queries.get(i);
            double result = -1.0;
            if (map.containsKey(query.get(0)) && map.containsKey(query.get(1))) {
                int ia = map.get(query.get(0)), ib = map.get(query.get(1));
                if (graph[ia][ib] > 0) {
                    result = graph[ia][ib];
                }
            }
            ret[i] = result;
        }
        return ret;
    }

}
